#-*- coding:utf-8 -*-
'''
进化算法求解全排列的最大值对应的组合
如：
[1,2,3] = 1*1+2*2+3*3=14
[3,2,1] = 1*3+2*2+3*1=10
[2,3,1] = 1*2+2*3+3*1=11
...
最后求解结果应该为[1,2,3]，对应适应值为14
'''

# json模块
import json
# 随机数模块
import random, csv
# 时间模块
import time, os, math
# 高性能数组模块
import numpy as np

# 进化算法模块inspyred
from inspyred import ec
from inspyred import swarm
from inspyred.ec import terminators
from inspyred.ec import observers
from inspyred.ec import analysis
import inspyred

import itertools
import pandas as pd

# 全排列模块
from itertools import permutations
# 欧式距离
from numpy.linalg import norm as np_linalg_norm

# 适应值曲线绘制模块
import ea_utils

import multiprocessing  # 多进程
import platform

# 小数点个数
DOUBLE_PRECISION = 6

# 清屏
def clear_dis():
    if platform.uname()[0] == 'Windows':
        os.system('cls')
    else:
        os.system('clear')

def get_dict_value(kwargs, key, value):
    if key in kwargs:
        return kwargs[key]
    else:
        return value

def creat_dir(dirs):
    if not os.path.exists(dirs):
        os.makedirs(dirs)

# 问题定义类
class My_problem():
    def __init__(self,args):
        self.lb = args.get('lb',0)
        self.ub = args.get('ub',1)
        self.comb_list = args.get("comb_list",[])
        
    # 随机生成一个在上下限范围内的编码
    # random -- 随机数生成器对象
    def rand(self, rng):
        lub = []
        for i,vt in enumerate(self.lb):
            lub.append(rng.choice(range(self.lb[i], self.ub[i])))
        return lub
    
    # 将个体编码(将索引转换为列表对应的组合)
    def decode(self, X):
        d_x = X[0]
        return self.comb_list[d_x]

    def fitness(self, X):
        X_list = self.decode(X)
        f = 0
        for i,_x in enumerate(X_list):
            # 判断是否是字母，如果是则转换为数字
            # ord('a')为97，ord('z')为122，因此对字母转换数字并取97的余数
            if type(_x) == str:
                _x = ord(_x)%97+1
            f += (i+1)*_x
        return f
    
    def generator(self, random, args):
        return self.rand(random)
        
    def evaluator(self, candidates, args):
        fitness = []
        for X in candidates:
            score = self.fitness(X)
            #添加到列表
            fitness.append(score)
        return fitness

def _my_avg_terminator(population, num_generations, num_evaluations, args):
    if num_generations > args['max_generations']:
        return True
    tolerance = args.setdefault('tolerance', 0.001)
    pop_fit = [x.fitness for x in population]
    avg_fit = sum(pop_fit) / float(len(population))
    best_fit = max(pop_fit)
    clear_dis()
    msg = '%.1lf%%'%((num_generations)*1.0/(args['max_generations'])*100)
    print('正在计算...完成%s'%msg)
    print('迭代次数:%d'%num_evaluations)
    if abs(best_fit - avg_fit) < tolerance and best_fit < args['minimum_fitness']:
        print('迭代收敛',best_fit, avg_fit, best_fit)
        return True
    return False

# 自定义终止条件
# 根据指定的类型来选择终止条件函数
def my_terminator(terminator_type):
    TerminatorDict = {
        # 按进化代数终止: 表示进化多少代之后就终止,无论是否达到最优,也不考虑算法是否收敛
        1:terminators.generation_termination,
        # 按适应值计算次数终止: 表示适应值计算多少次后就就终止,无论是否达到最优,也不考虑算法是否收敛
        2:terminators.evaluation_termination,
        # 按种群的平均适应值终止: 表示种群的平均适应值连续多少代没有显著变化就终止,因为进化过程已经收敛或者假收敛了
        3:terminators.average_fitness_termination,
        # 自定义终止条件，表示迭代无显著变化且达到设定精度则终止
        4:_my_avg_terminator,
        # 不增长终止：表示一定代数内适应值无变化之后终止
        5:terminators.no_improvement_termination
    }
    if not (terminator_type in TerminatorDict):
        terminator_type = 1
    return TerminatorDict[terminator_type]

def generate_rastrigin(random, args):
    return args['problem'].generator(random, args)

def evaluate_rastrigin(candidates, args):
    return args['problem'].evaluator(candidates, args)

# 自定义个体生成器
# 注: 下面es.evolve()函数中的所有参数构成了一个词典args
def my_generator(random, args):
    # 跳转到Problem::rand()成员函数
    return args['problem'].rand(random)

# 自定义个体适应值计算函数
def my_fitness(X, args):
    # 跳转到Problem::fitness()成员函数
    return args['problem'].fitness(X)

# 自定义种群适应值计算函数
# 注: 参数candidates是一个数组,它由多个个体组成
def my_evaluator(candidates, args):
    #依次计算每个个体的适应值
    fitness = []
    for X in candidates:
        # 将浮点数四舍五入,强制转换为0和1,并计算个体的适应值
        score = my_fitness(X, args)
        #添加到列表
        fitness.append(score)
    return fitness

# inspyred进化算法主框架
def run_inspyred_ea(args):
    #随机数初始化
    rng = random.Random()
    rng.seed(int(time.time()))
    algo = args.get('algo', 1)
    es = None
    if algo == 'ga':
        # 遗传算法
        es = ec.GA(rng)
    elif algo == 'pso':
        # 粒子群算法
        es = swarm.PSO(rng)
        es.topology = swarm.topologies.ring_topology
    elif algo == 'sa':
        # 模拟退火算法
        es = ec.SA(rng)
    elif algo == 'dea':
        # 差分进化算法
        es = ec.DEA(rng)
    elif algo == 'es':
        # 进化策略算法
        es = ec.ES(rng)    
    else:
        # 默认采用遗传算法
        es = ec.GA(rng)
    # 整数与实数编码的范围设定不一样
    if args.get('type','') == 'int':
        bounder = inspyred.ec.DiscreteBounder(np.arange(min(args['lb']),max(args['ub'])))
    else:
        bounder = inspyred.ec.Bounder(args['lb'],args['ub'])
    #设置终止条件
    es.terminator = my_terminator(args['terminator'])
    stat_file = None
    ind_file = None
    if args['file_observe']:
        es.observer = observers.file_observer
        # 新建种群数据记录文件
        stat_file = open(args['stat_file'], 'w')
        ind_file = open(args['ind_file'], 'w')   
    problem = My_problem(args)
    if args['use_palla']:
        final_pop = es.evolve(
                            generator=generate_rastrigin, 
                            evaluator=inspyred.ec.evaluators.parallel_evaluation_mp,
                            mp_evaluator=evaluate_rastrigin, 
                            mp_nprocs=args.get('mp_nprocs',4),
                            pop_size=args.get('popsize', 10), 
                            bounder=bounder,
                            maximize=args.get('maximize',False),
                            max_evaluations = args.get('max_evaluations', 1200),   # 最大适应值计算次数
                            max_generations = args.get('max_generations', 200),
                            statistics_file = stat_file, 
                            individuals_file = ind_file, 
                            problem = problem,
                            # 遗传算法GA参数
                            mutation_rate = args.get('mutation_rate',0.015),       # 变异率
                            cross_rate =  args.get('cross_rate',0.75),            # 交叉率
                            # 粒子群算法PSO参数
                            neighborhood_size =  args.get('neighborhood_size',5),  # 邻域范围
                            minimum_fitness = args.get('minimum_fitness',0.1),
                            #   差分进化
                            crossover_rate = 0.75)
    
    else:
        final_pop = es.evolve(
                            generator = my_generator,                              # 自定义个体生成函数
                            evaluator = my_evaluator,                              # 自定义个体适应值计算函数
                            pop_size=args.get('popsize', 10), 
                            bounder=bounder,
                            maximize=args.get('maximize',False),
                            max_evaluations = args.get('max_evaluations', 1200),   # 最大适应值计算次数
                            max_generations = args.get('max_generations', 20),
                            statistics_file = stat_file, 
                            individuals_file = ind_file, 
                            problem = problem,
                            # 遗传算法GA参数
                            mutation_rate = args.get('mutation_rate',0.015),       # 变异率
                            cross_rate =  args.get('cross_rate',0.75),            # 交叉率
                            # 粒子群算法PSO参数
                            neighborhood_size =  args.get('neighborhood_size',5),  # 邻域范围
                            minimum_fitness = args.get('minimum_fitness',0.1),
                            #   差分进化
                            crossover_rate = 0.75)

    # 关闭种群数据记录文件
    if args['file_observe']:
        stat_file.close()
        ind_file.close()
    final_pop.sort(reverse = True)
    return final_pop[0].candidate,final_pop[0].fitness

def ea_test(config):
    start = time.time()
    # 遗传算法计算得到"最优"个体
    best_X,best_fitness = run_inspyred_ea(config)
    # 结束时间
    stop = time.time()
    print('计算耗时:', "%.1fs" % (stop-start))
    return best_X,best_fitness

if __name__ == '__main__':
    # 需要排列的列表
    # 1. 数字排列，可以为浮点数，也可以是整数
    # init_list = [100.5,1,10,2,4,3]
    init_list = [1,2,3,4]
    # 2. 字母排列只需要修改这个位置
    # init_list = ['z','a','b','c']
    # 3. 字母与数字混合排列
    # init_list = ['z','a','b','c',15]
    # 全排列列表
    comb_list = [list(_comb_list) for _comb_list in permutations(init_list)]
    # 保存的路径
    out_dir = './out/test/'
    creat_dir(out_dir)
    # 参数设置
    config = {
        #---------------- 自定义参数: 变量及范围  -----------------#
        # 全排列列表
        "comb_list":comb_list,
        # 下限，范围表示全排列列表索引范围
        "lb":[0],
        # 上限(数组中的每一位代表一个变量的上限)
        "ub":[len(comb_list)],
        # 目标值最大化还是最小化，True表示求最大适应值
        "maximize":True,
        # 是否使用并行
        "use_palla":False,
        # 是否保存适应值监测文件
        "file_observe":True,
        # 状态监测文件路径
        "stat_file":out_dir+'state.csv',
        # 目标值监测文件路径
        "ind_file":out_dir+'ind_file.csv',
        # 编码为整数还是浮点数，对于目前这个问题，索引就是整数
        'type':'int',
        #---------------- 自定义参数: 距离度量方法及终止条件  -----------------#
        "algo":"es",                     # 算法选择
                                        #   1. 遗传算法ga
                                        #   2. 粒子群算法pso
                                        #   3. 模拟退火算法sa
                                        #   4. 差分进化算法dea
                                        #   5. 进化策略es
                
        "terminator": 5,                # 终止条件(1-表示按最大进化代数终止迭代)
                                        #   1. 按最大进化代数终止迭代
                                        #   2. 按最大适应值计算次数终止迭代
                                        #   3. 按种群平均适应值收敛终止迭代
                                        #   4. 自定义终止条件，表示迭代无显著变化且达到设定精度则终止
                                        #   5. 不增长终止：表示一定代数内适应值无变化之后终止

        #---------------- 进化算法通用参数(遗传、粒子群、蚁群、模拟退火等)  -----------------#
        "popsize": 50,                  # 种群规模
        "max_generations": 100,        # 最大进化代数
        "max_evaluations": 1000,        # 最大适应值计算次数(暂未使用)

        #---------------- 遗传算法GA参数 --------------------#
        "cross_rate": 0.9,             # 交叉率(默认1.0)
        "mutation_rate": 0.015,         # 变异率(默认0.1)

        #---------------- 粒子群算法PSO参数 -----------------#
        "neighborhood_size": 5,          # 邻域范围
    }
    best_X,best_fitness = ea_test(config)
    # 最佳组合索引
    best_X = int(best_X[0])
    # 绘制迭代图
    ea_utils.plot(config['stat_file'], out_dir+'ea.png', False)
    print('最优解:',comb_list[best_X])
    print('最优解对应的适应值:',best_fitness)
